﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _03_二叉树
{
   class BiTree
   {
      public BiNode Head { get; set; }

      public BiTree()
      {
         this.Head = null;
      }

      // 先序遍历二叉树 递归
      private void _PreOrder_Recursive(BiNode node, Action<int> action)
      {
         action.Invoke(node.val);   // 第1次访问
         if (node.lchild != null)
            _PreOrder_Recursive(node.lchild, action);
         if (node.rchild != null)
            _PreOrder_Recursive(node.rchild, action);
      }
      public void PreOrder_Recursive(Action<int> action)
      {
         _PreOrder_Recursive(this.Head, action);
      }

      // 中序遍历二叉树 递归
      private void _InOrder_Recursive(BiNode node, Action<int> action)
      {
         if (node.lchild != null)
            _InOrder_Recursive(node.lchild, action);
         action.Invoke(node.val);   // 第2次访问
         if (node.rchild != null)
            _InOrder_Recursive(node.rchild, action);
      }
      public void InOrder_Recursive(Action<int> action)
      {
         _InOrder_Recursive(this.Head, action);
      }

      // 后序遍历二叉树 递归
      private void _PostOrder_Recursive(BiNode node, Action<int> action)
      {
         if (node.lchild != null)
            _PostOrder_Recursive(node.lchild, action);
         if (node.rchild != null)
            _PostOrder_Recursive(node.rchild, action);
         action.Invoke(node.val);   // 第3次访问
      }
      public void PostOrder_Recursive(Action<int> action)
      {
         _PostOrder_Recursive(this.Head, action);
      }

      // 先序遍历二叉树 非递归
      public void PreOrder(Action<int> action)
      {
         if (this.Head == null)
            return;
         Stack<BiNode> s = new Stack<BiNode>();
         s.Push(this.Head);
         BiNode p;
         while (s.Count != 0)
         {
            p = s.Pop();
            action.Invoke(p.val);
            if (p.rchild != null)
               s.Push(p.rchild);
            if (p.lchild != null)
               s.Push(p.lchild);
         }
      }

      // 后序遍历二叉树 非递归
      public void PostOrder(Action<int> action)
      {
         if (this.Head == null)
            return;
         Stack<BiNode> s1 = new Stack<BiNode>();
         Stack<BiNode> s2 = new Stack<BiNode>();
         s1.Push(this.Head);
         BiNode p;
         while (s1.Count != 0)
         {
            p = s1.Pop();
            s2.Push(p);
            if (p.lchild != null)
               s1.Push(p.lchild);
            if (p.rchild != null)
               s1.Push(p.rchild);
         }
         while (s2.Count != 0)
         {
            p = s2.Pop();
            action.Invoke(p.val);
         }
      }

      // 中序遍历二叉树 非递归
      public void InOrder(Action<int> action)
      {
         if (this.Head == null)
            return;
         BiNode p = this.Head;
         Stack<BiNode> s = new Stack<BiNode>();
         while (p != null || s.Count != 0)
         {
            if (p != null)
            {
               s.Push(p);
               p = p.lchild;
            }
            else
            {
               p = s.Pop();
               action.Invoke(p.val);
               p = p.rchild;
            }
         }
      }

      // 层次遍历
      public void BFS(Action<int> action)
      {
         if (this.Head == null)
            return;
         Queue<BiNode> q = new Queue<BiNode>();
         q.Enqueue(this.Head);
         BiNode p;
         while (q.Count != 0)
         {
            p = q.Dequeue();
            action.Invoke(p.val);
            if (p.lchild != null)
               q.Enqueue(p.lchild);
            if (p.rchild != null)
               q.Enqueue(p.rchild);
         }
      }

      // 二叉树的深度
      private static int _GetDepth_Process(BiNode node)
      {
         if (node == null)
            return 0;
         int ld = _GetDepth_Process(node.lchild);
         int rd = _GetDepth_Process(node.rchild);
         return (Math.Max(ld, rd) + 1);
      }
      public int GetDepth()
      {
         return _GetDepth_Process(this.Head);
      }

      // 二叉树的最大宽度
      private struct MaxDistanceRType
      {
         public int maxDis;   // 最大距离
         public int height;   // 高度

         public MaxDistanceRType(int maxDis, int height)
         {
            this.maxDis = maxDis;
            this.height = height;
         }
      }
      private MaxDistanceRType _GetMaxDistance_Process(BiNode node)
      {
         if (node == null)
            return new MaxDistanceRType(0, 0);

         // 拿到左子树信息
         MaxDistanceRType lData = _GetMaxDistance_Process(node.lchild);
         // 拿到右子树信息
         MaxDistanceRType rData = _GetMaxDistance_Process(node.rchild);

         // 合成信息
         int height = Math.Max(lData.height, rData.height) + 1;
         int maxDisWithHead = height;  // 头结点参与
         int maxDisWithoutHead = Math.Max(lData.maxDis, rData.maxDis);  // 头结点不参与
         int maxDis = Math.Max(maxDisWithHead, maxDisWithoutHead);

         return new MaxDistanceRType(maxDis, height);
      }
      public int GetMaxDistance()
      {
         return _GetMaxDistance_Process(this.Head).maxDis;
      }

      // 判断是否为搜索二叉树
      private bool _IsBST_Process(BiNode node, ref int maxVal)
      {
         if (node == null)
            return true;
         // 左树信息
         bool lRes = _IsBST_Process(node.lchild, ref maxVal);
         // 合成信息
         if (!lRes || node.val <= maxVal)
            return false;
         maxVal = node.val;
         return lRes && _IsBST_Process(node.rchild, ref maxVal);
      }
      public bool IsBST()
      {
         int maxVal = int.MinValue;
         return _IsBST_Process(this.Head, ref maxVal);
      }

      // 判断是否为满二叉树
      private struct FT_RType
      {
         public int depth; // 深度
         public int count; // 结点个数

         public FT_RType(int depth, int count)
         {
            this.depth = depth;
            this.count = count;
         }
      }
      private FT_RType _IsFT_Procees(BiNode node)
      {
         if (node == null)
            return new FT_RType(0, 0);
         FT_RType lData = _IsFT_Procees(node.lchild);
         FT_RType rData = _IsFT_Procees(node.rchild);
         int depth = Math.Max(lData.depth, rData.depth) + 1;
         int count = lData.count + rData.count + 1;
         return new FT_RType(depth, count);
      }
      public bool IsFT()
      {
         FT_RType res = _IsFT_Procees(this.Head);
         return (res.count == ((1 << res.depth) - 1));   // n = 2^k - 1
      }

      // 判断是否为平衡二叉树
      private struct BT_RType
      {
         public int depth; // 深度
         public bool isBT; // 是否为平衡二叉树

         public BT_RType(int depth, bool isBT)
         {
            this.depth = depth;
            this.isBT = isBT;
         }
      }
      private BT_RType _IsBT_Process(BiNode node)
      {
         if (node == null)
            return new BT_RType(0, true);
         BT_RType lData = _IsBT_Process(node.lchild);
         BT_RType rData = _IsBT_Process(node.rchild);
         int depth = Math.Max(lData.depth, rData.depth) + 1;
         bool isBT = lData.isBT && rData.isBT &&
            (Math.Abs(lData.depth - rData.depth) <= 1);
         return new BT_RType(depth, isBT);
      }
      public bool IsBT()
      {
         return _IsBT_Process(this.Head).isBT;
      }

      // 判断完全二叉树
      public bool IsCT()
      {
         if (this.Head == null)
            return false;
         Queue<BiNode> queue = new Queue<BiNode>();
         queue.Enqueue(Head);
         BiNode cur;
         bool flag = false;   // 遇到左右两孩子不双全的情况 标记
         // 层次遍历
         while (queue.Count != 0)
         {
            cur = queue.Dequeue();
            // 有右无左 -> FALSE
            if (cur.rchild != null && cur.lchild == null)
               return false;
            // 第一次遇到左右两孩子不双全的情况
            if (cur.rchild == null || cur.lchild == null)
               flag = true;
            // 若遇到上述情况，后续均为叶子节点
            if (flag && cur.lchild != null)
               return false;
            // 左右子树入队
            if (cur.lchild != null)
               queue.Enqueue(cur.lchild);
            if (cur.rchild != null)
               queue.Enqueue(cur.rchild);
         }
         return true;
      }

      // 找到两个结点的最低公共祖先
      private void _GetAncestor_Traverse_Process(
         BiNode node,
         Dictionary<BiNode, BiNode> parents)
      {
         if (node.lchild != null)
         {
            parents.Add(node.lchild, node);
            _GetAncestor_Traverse_Process(node.lchild, parents);
         }
         if (node.rchild != null)
         {
            parents.Add(node.rchild, node);
            _GetAncestor_Traverse_Process(node.rchild, parents);
         }
      }
      public BiNode GetAncestor(BiNode node1, BiNode node2)
      {
         // 构建二叉树的父节点指向
         Dictionary<BiNode, BiNode> parentNodes = new Dictionary<BiNode, BiNode>();
         parentNodes.Add(this.Head, null);
         _GetAncestor_Traverse_Process(this.Head, parentNodes);

         // 构建node1的父结点查询集合
         HashSet<BiNode> hashset = new HashSet<BiNode>();
         BiNode cur = node1;
         while (cur != null)
         {
            hashset.Add(cur);
            cur = parentNodes[cur];
         }

         // 查询node2的父节点与查询集合的交集部分
         cur = node2;
         while (cur != null)
         {
            if (hashset.Contains(cur))
               return cur;
            cur = parentNodes[cur];
         }

         return null;
      }

      // 公共祖先问题递归版本
      private BiNode _GetAncestor_Recursive_Process(BiNode node, BiNode o1, BiNode o2)
      {
         if (node == null || node == o1 || node == o2)
            return node;
         BiNode left = _GetAncestor_Recursive_Process(node.lchild, o1, o2);
         BiNode right = _GetAncestor_Recursive_Process(node.rchild, o1, o2);
         if (left != null && right != null)
            return node;
         return left ?? right;
      }
      public BiNode GetAncestor_Recursive(BiNode o1, BiNode o2)
      {
         return _GetAncestor_Recursive_Process(this.Head, o1, o2);
      }

      // 二叉树的序列化
      private static string _Serialize_Process(BiNode node)
      {
         if (node == null)
            return "#_";
         return node.val.ToString() + "_" +
            _Serialize_Process(node.lchild) +
            _Serialize_Process(node.rchild);
      }

      public static string Serialize(BiNode head)
      {
         return _Serialize_Process(head);
      }

      // 二叉树的反序列化
      private static BiNode _Deserialize_Process(string[] splits, ref int i)
      {
         if (splits[i] == "#")
         {
            i++;
            return null;
         }
         BiNode node = new BiNode(Convert.ToInt32(splits[i++]));
         node.lchild = _Deserialize_Process(splits, ref i);
         node.rchild = _Deserialize_Process(splits, ref i);
         return node;
      }

      public static BiNode Deserialize(string str)
      {
         // 按'_'分割字符串
         string[] splits = str.Split("_");
         // 返回反序列化二叉树
         int i = 0;
         return _Deserialize_Process(splits, ref i);
      }

      // 凹凸折纸问题
      private static void _Orikami_Process(int count, int i, string str)
      {
         if (count == i)
            return;
         _Orikami_Process(count, i + 1, "凹");
         Console.WriteLine($"{i + 1}{str}");
         _Orikami_Process(count, i + 1, "凸");
      }
      public static void Orikami(int count)
      {
         _Orikami_Process(count, 0, "凹");
      }
   }
}
